#include <stdio.h>
#include <stdlib.h>

typedef int ElemType;

// 链表节点定义
typedef struct Node {
    ElemType data;
    struct Node* next;
} Node;

// 链表定义
typedef struct {
    Node* head;
} List;

// 初始化链表
void InitList(List* L) {
    L->head = NULL;
}

// 获取链表长度
int ListLength(List L) {
    int length = 0;
    Node* temp = L.head;
    while (temp != NULL) {
        length++;
        temp = temp->next;
    }
    return length;
}

// 获取链表中的第i个元素
void GetElem(List L, int i, ElemType* e) {
    Node* temp = L.head;
    int count = 1;
    while (temp != NULL && count < i) {
        temp = temp->next;
        count++;
    }
    if (temp != NULL) {
        *e = temp->data;
    } else {
        printf("Error: Invalid position.\n");
    }
}

// 查找链表中是否存在某元素
int LocateElem(List L, ElemType e) {
    Node* temp = L.head;
    while (temp != NULL) {
        if (temp->data == e) {
            return 1;
        }
        temp = temp->next;
    }
    return 0;
}

// 插入元素到链表末尾
void ListInsert(List* L, ElemType e) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = e;
    newNode->next = NULL;
    
    if (L->head == NULL) {
        L->head = newNode;
    } else {
        Node* temp = L->head;
        while (temp->next != NULL) {
            temp = temp->next;
        }
        temp->next = newNode;
    }
}

// 合并集合A和B，A = A ∪ B
void unionList(List* La, List Lb) {
    Node* tempB = Lb.head;
    ElemType e;

    // 遍历线性表Lb
    while (tempB != NULL) {
        e = tempB->data;
        // 如果La中不存在该元素，则插入
        if (!LocateElem(*La, e)) {
            ListInsert(La, e);
        }
        tempB = tempB->next;
    }
}

// 打印链表
void PrintList(List L) {
    Node* temp = L.head;
    while (temp != NULL) {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("\n");
}

int main() {
    List La, Lb;
    InitList(&La);
    InitList(&Lb);

    // 向La中插入元素
    ListInsert(&La, 1);
    ListInsert(&La, 2);
    ListInsert(&La, 3);
    
    // 向Lb中插入元素
    ListInsert(&Lb, 3);
    ListInsert(&Lb, 4);
    ListInsert(&Lb, 5);

    printf("La: ");
    PrintList(La);
    printf("Lb: ");
    PrintList(Lb);

    // 合并La和Lb
    unionList(&La, Lb);

    printf("La ∪ Lb: ");
    PrintList(La);

    return 0;
}
